package problem76_Minimum_Window_Substring;

public class Solution {
	    int initTargetHash(int []targethash, String Target) {
	        int targetnum =0 ;
	        for (char ch : Target.toCharArray()) {
	            targetnum++;
	            targethash[ch]++;
	        }
	        return targetnum;
	    }
	    public String minWindow(String Source, String Target) {
	        // queueing the position that matches the char in T
	        int ans = Integer.MAX_VALUE;
	        String minStr = "";
	        
	        int[] targethash = new int[256];
	        
	        int targetnum = initTargetHash(targethash, Target);
	        int sourcenum = 0;
	        int j = 0, i = 0;
	        for(i = 0; i < Source.length(); i++) {
	            if(targethash[Source.charAt(i)] > 0)
	                sourcenum++;
	            
	            targethash[Source.charAt(i)]--;
	            while(sourcenum>=targetnum) {
	                if(ans > i - j + 1) {
	                    ans = Math.min(ans, i - j + 1);
	                    minStr = Source.substring(j, i + 1);
	                }
	                targethash[Source.charAt(j)]++;
	                if(targethash[Source.charAt(j)] > 0)
	                    sourcenum--;
	                j ++;
	            }
	        }
	        return minStr;
	    }
	    
	    public static void main(String[] args){
	    	System.out.println(new Solution().minWindow("ACAB", "AB"));
	    }
}
